/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  quickSort(nums, 0, nums.length - 1)
  return nums
};
//快速排序
function quickSort(nums, left, right) {
  if (left >= right) return

  //随机索引
  const randomIndex = left + Math.floor(Math.random() * (right - left + 1));
  //把索引randomIndex和索引right的数组元素交换
  [nums[randomIndex], nums[right]] = [nums[right], nums[randomIndex]]

  //基准索引：调用分区函数，找到nums[right]在排序后数组的索引位置
  let pivotIndex = partition(nums, left, right)
  quickSort(nums, left, pivotIndex - 1)
  quickSort(nums, pivotIndex + 1, right)
}

function partition(nums, left, right) {
  //基准元素：nums[right]
  const pivotValue = nums[right]
  let storeIndex = left

  //遍历i从left到right-1：如果nums[i]小于基准元素pivotValue，交换索引storeIndex和索引i的数组元素，storeIndex++
  //最终storeIndex停留的位置就是基准元素pivotValue的基准索引
  for (let i = left; i < right; i++) {
    if (nums[i] < pivotValue) {
      [nums[storeIndex], nums[i]] = [nums[i], nums[storeIndex]]
      storeIndex++
    }
  }

  //交换索引storeIndex和索引right的数组元素
  [nums[storeIndex], nums[right]] = [nums[right], nums[storeIndex]]

  //返回基准索引
  return storeIndex
}